1. Field of the Invention
The present invention relates to a method for controlling access to data stored in a buffer memory, and more particularly to a method for controlling access to a buffer which is suitable in quickly determining whether a required data is stored in the buffer memory or not
2. Description of the Prior Art
In a system, such as a data base system which contains a large volume of data, and repeatedly reads out such data and processes them, high speed readout of the data is required.
In a relational data base system, a large volume of data is stored in an external storage, such as a magnetic disk device. Areas on the disk are divided into blocks which are called pages, and the data on the disk is read and transferred from the disk to a main storage for each data block. The transferred data block is stored in a buffer area in the main storage for utilization.
The relational data base system has been well known, for example, by "RELATIONAL DATA BASE SYSTEMS: WHERE WE STAND TODAY", papers of conference "INFORMATION PROCESSING 80", published by North-Holland Publishing Company.
A prior art method to control the data block transferred to the buffer area of the main storage is described below.
The transferred data block is written into the buffer area in accordance with a start address of the designated area in which the data block is to be written. The data block next transferred is also stored at the designated address. The address is stored in the previous buffer area as an address (pointer) for accessing the data block to be next connected. The data blocks transferred subsequently are stored in a similar manner. This method is called a chaining method. Start address of the chain is separately stored.
The chaining method may be one which chains in the order of transfer as described above or one which alters the chain so that a most recently referenced data block comes to the top position.
In processing data of the data base, if a necessary data is stored in the buffer area, it is utilized, and if it is not stored, the data block is fetched from the external storage and stored in the buffer area for utilization.
In a prior art control method, in order to determine whether the required data block is in the buffer or not, the chain must be serially searched and therefore, a long search time is required. In order to resolve the above problem there is assumed a search method which uses a hashing technique to restrict search items to a portion of the chain. However, it still needs a serial search and cannot sufficiently shorten the search time.